package leetcode.prefixSum;

class NumMatrix {

    private final int[][] matrix;
    private final int[][] prefix;
    private final int m;
    private final int n;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.prefix = new int[m][n];
        getPrefix();
    }

    private void getPrefix() {
        // 遍历每一行，计算每一行的前缀和
        for (int i = 0; i < m; i++) {
            prefix[i][0] = matrix[i][0];
            // 计算一行的前缀和
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i][j - 1] + matrix[i][j];
            }
        }
        // 遍历每一列，计算以当前元素为右下角的矩阵的元素和
        for (int j = 0; j < n; j++) {
            // 遍历一列
            for (int i = 1; i < m; i++) {
                prefix[i][j] = prefix[i][j] + prefix[i - 1][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = 0;
        if (row1 > 0 && col1 > 0) {
            ans = prefix[row2][col2] - prefix[row2][col1 - 1] - prefix[row1 - 1][col2] + prefix[row1 - 1][col1 - 1];
        } else if (row1 == 0 && col1 > 0) {
            ans = prefix[row2][col2] - prefix[row2][col1 - 1];
        } else if (row1 > 0 && col1 == 0) {
            ans = prefix[row2][col2] - prefix[row1 - 1][col2];
        } else if (row1 == 0 && col1 == 0) {
            ans = prefix[row2][col2];
        }
        return ans;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
public class leetcode304 {
    public static void main(String[] args) {
        int[][] matrix = {{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}};
        NumMatrix numMatrix = new NumMatrix(matrix);
        System.out.println(numMatrix.sumRegion(2, 1, 4, 3)); // return 8
        System.out.println(numMatrix.sumRegion(1, 1, 2, 2)); // return 11
        System.out.println(numMatrix.sumRegion(1, 2, 2, 4)); // return 12
    }
}
